package agent;

import java.util.LinkedList;

public class Combinations {

    public static LinkedList<int[]> computeCombinations(int n, int k) {
        LinkedList<int[]> combinations = new LinkedList();
        int[] combination = new int[k];

        for (int i = 0; i < k; ++i) {
            combination[i] = i;
        }

        combinations.add(combination);
        boolean more;
        do {
            combination = combination.clone();
            more = nextCombination(combination, n, k);
            if (more) {
                combinations.add(combination);
            }
        } while (more);

        return combinations;
    }

    private static boolean nextCombination(int combination[], int n, int k) {
        int i = k - 1;
        ++combination[i];
        while (i > 0 && combination[i] >= n - k + 1 + i) {
            --i;
            ++combination[i];
        }

        if (combination[0] > n - k) {
            return false;
        }

        for (i = i + 1; i < k; ++i) {
            combination[i] = combination[i - 1] + 1;
        }
        
        return true;
    }

    public static int getNumCombinations(int n, int k) {
        int aux = n - k;

        int numerator = 1, denominator = 1;
        for (int i = 1; i <= aux; i++) {
            numerator *= n - i + 1;
            denominator *= i;
        }

        return numerator / denominator;
    }    
}
